# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root=TreeNode(5,None)
root.left=TreeNode(1,None)
root.right=TreeNode(4,None)
root.right.left=TreeNode(3,None)
root.right.right=TreeNode(6,None)

#法子有问题
def dfs(curRoot,rootVal):
    leftFlag=None
    rightFlag=None
    #出口条件
    if curRoot.left==None and curRoot.right==None:
        #整个该分支是正确的
        return True
    if curRoot.left!=None:
        print("left_root_val:",rootVal)
        if curRoot.left.val<rootVal:
            leftFlag=dfs(curRoot.left,curRoot.left.val)
        else:
            return False
    if curRoot.right!=None:
        print("right_root_val:",rootVal)
        if curRoot.right.val>rootVal:
            rightFlag=dfs(curRoot.right,rootVal)
        else:
            return False
    print("leftFlag=",leftFlag," rightFlag=",rightFlag)
    #综合判断一下
    if (leftFlag==None or leftFlag==True) and (rightFlag==None or rightFlag==True):
        return True
    else:
        return False

def dfs1(path,root):
    if root.left==None and root.right==None:
        path.append(root.val)
        return None
    #先存左子树结点
    dfs1(path,root.left)
    #存根节点
    path.append(root.val)
    #存右子树结点
    dfs1(path,root.right)


def isValidBST(root):
    path=[]
    dfs1(path,root)
    print(path)
    if len(path)<=1:
        return True
    path_pre=path[0]
    for i in range(1,len(path)):
        if path_pre>path[i]:
            return False
        path_pre=path[i]
    return True

print(isValidBST(root))
